This invention relates to the field of computer software that recognizes shapes drawn by a user.
In the field of computer systems with graphical interfaces, it is sometimes necessary for the computer to allow a user to draw a shape or figure on the computer screen. Users typically draw shapes or figures on the computer screen through an input device, such as a touch-sensitive screen, mouse, track ball, tablet, or similar input device that captures the user's hand movements and translates these movements into figures on the screen. In the field of handheld computers, many user interfaces employ a stylus and a touch sensitive screen. For example, U.S. Pat. No. 4,972,496 to Sklarew, “Handwritten keyboardless entry computer system,” discloses the combination of a touch-sensitive screen laid over a liquid crystal display matrix. Computer systems that allows users to draw shapes directly on the screen by converting hand movements into “freehand” lines and curves on the screen are well known in the art.
A known problem with this freehand method of drawing is that drawings can appear to be unclear. Because these drawings are typically done without the aid of a straightedge or other drafting apparatus, lines and curves drawn by the user's hand can appear to be crooked, uneven, and jagged. Further, a touch sensitive matrix laid over a display screen sometimes has a lower resolution than the resolution of the display screens. This results in undesirable drawings that are unclear.
A solution to this problem is to program the computer system to analyze the shapes drawn by a user, determine what shapes the user drew, and re-draw those shapes using straight lines and smooth curves. Such systems typically perform three steps.
First, this system allows the user to draw a freehand drawing through the use of an input device, such as a touch sensitive screen. Second, the system performs an analysis of the user's drawing. Third, the system erases the user's freehand drawing and draws a perfected drawing using the drawing analysis made in the prior step. This drawing is typically made through any of a number of prior art methods that are well known in the field.
One prior art system described in Theo Pavlidis & Christopher J. Van Wyk, “An Automatic Beautifier for Drawings and Illustrations,” Siggraph vol. 19, pp. 225-234, San Francisco, Jul. 22-26, 1985 [hereinafter “Pavlidis & Van Wyk”] used a clustering technique. Pavlidis & Van Wyk disclose a system that groups together sets of points drawn by the user when the difference in values in the distance between adjacent elements is less than some small constant. Following this grouping, the clustering algorithm disregards clusters that are wider than some other predefined constant, and splits clusters in two when their width indicates they may contain more than one line. The algorithm then derives equations that can be used to draw lines. The Pavlidis & Van Wyk system does not store or analyze data such as the order in which the user drew each point or the speed with which each point was drawn. The Pavlidis & Van Wyk system produces undesirable results when it is applied to drawings that contain a large number of points, especially drawings that contain closely overlapping lines, because it depends on the proper prior selection of the aforementioned constants in order to distinguish between closely spaced lines.
Another prior art system disclosed by Bozinovic et al. in U.S. Pat. No. 5,544,265, “Shape recognizer for graphical computer systems” records the speed and trajectory of a stylus as it passes over a screen. Bozinovic discloses a system that analyzes drawings by determining line segment end points and then determining whether segments between end points are straight or curved. Bozinovic does not disclose a method by which the system determines the location of the end points or how the system determines whether a segment is straight. Bozinovic requires a number of computationally expensive calculations.
Another prior art system is described in Joaquim A. Jorge & Manuel J. Fonseca, “A Simple Approach to Recognise Geometric Shapes Interactively,” Departamento de Engenharia Informática, IST/UTL, Av. Rovisco Pais, 1049-001 Lisboa, Portugal [hereinafter “Jorge & Fonesca.”] Jorge & Fonesca analyzed drawings by calculating geometric characteristics of the user's drawing, and comparing these geometric characteristics to those of a set of known ideal figures. Jorge & Fonesca's method calculates the convex hull, smallest-area regular polygons, perimeter and area scalar ratios of the user's drawing and compares these characteristics with the characteristics of known figures. This method has the disadvantage of recognizing only those ideal figures that were anticipated by the system's designers. If a user draws a figure that the system's designers did not anticipate, it will not correctly recognize it, because it will be unable to compare the drawing's geometric characteristics with ideal geometric characteristics for that figure. This system also carries an undesirable risk of incorrect analysis when two ideal figures, such as an isosceles triangle and a right triangle, have similar characteristics.